package com.ddshuai.easy;

import java.math.BigInteger;

/**
 * 描述 新通教育
 *
 * @author ddshuai
 * @date 2018-09-28 下午1:25
 * <p>
 * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
 * <p>
 * 给定一个数字 n，找出可形成完整阶梯行的总行数。
 * <p>
 * n 是一个非负整数，并且在32位有符号整型的范围内。
 * 示例 1:
 * n = 5
 * <p>
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤
 * <p>
 * 因为第三行不完整，所以返回2.
 * 示例 2:
 * n = 8
 * <p>
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤ ¤
 * ¤ ¤
 * <p>
 * 因为第四行不完整，所以返回3.
 **/
public class ArrangeCoins {

    /**
     * 效率低下  31.39%  58ms
     *
     * @param n
     * @return
     */
    public static int arrangeCoins(int n) {
        if (n < 2) {
            return n;
        }
        int sqrt = (int) Math.sqrt((long) n * 2);
        int sum = 0;
        for (int i = 0; i < sqrt; i++) {
            sum += i + 1;
        }
        if (sum < n) {
            while (sum < n) {
                sqrt++;
                sum += sqrt;
                if (sum < 0) {
                    //超出了数据范围
                    break;
                }
            }
            sqrt--;
        } else {
            while (sum > n) {
                sqrt--;
                sum -= sqrt;
            }
        }
        return sqrt;
    }

    /**
     * 性能一般 49.9% 50ms
     *
     * @param n
     * @return
     */
    public static int arrangeCoins1(int n) {
        //等差数列公式
        int result = 0;
        result = (int) Math.sqrt((long) n * 2);

        BigInteger bigInteger = new BigInteger(String.valueOf(result));
        BigInteger bigInteger1 = new BigInteger(String.valueOf(result + 1));
        BigInteger count = bigInteger.multiply(bigInteger1).divide(new BigInteger("2"));
        BigInteger target = new BigInteger(String.valueOf(n));
        //超出范围
        if (count.subtract(target).intValue() > 0) {
            while (count.subtract(target).intValue() > 0) {
                result--;
                BigInteger bigIntegera = new BigInteger(String.valueOf(result));
                BigInteger bigIntegerb = new BigInteger(String.valueOf(result + 1));
                count = bigIntegera.multiply(bigIntegerb).divide(new BigInteger("2"));
            }

        } else if (count.subtract(target).intValue() < 0) {
            while (count.subtract(target).intValue() < 0) {
                result++;
                BigInteger bigIntegera = new BigInteger(String.valueOf(result));
                BigInteger bigIntegerb = new BigInteger(String.valueOf(result + 1));
                count = bigIntegera.multiply(bigIntegerb).divide(new BigInteger("2"));
            }
            result--;
        }
        return result;
    }

    /**
     * 性能好  24ms 来自社区
     *
     * @param n
     * @return
     */
    public int arrangeCoins2(int n) {
        int left = 0;
        int hight = n;
        while (left < hight) {
            if ((left * (left - 1) / 2) == n) {
                return left;
            }
            long mid = left + (hight - left) / 2;
            if ((mid * (mid + 1) / 2) == n) {
                return (int) mid;
            }
            if ((mid * (mid + 1) / 2) > n) {
                hight = (int) (mid - 1);
            }
            if ((mid * (mid + 1) / 2) < n) {
                left = (int) (mid + 1);
            }
        }
        if (((long) left * ((long) left + 1L) / 2) > (long) n) {
            left--;
        }
        return left;
    }

    /**
     * 性能好  24ms 来自社区
     *
     * @param n
     * @return
     */
    public int arrangeCoins3(int n) {
        return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5);
    }

    public static void main(String[] args) {
//        System.out.println(arrangeCoins(1));
//        System.out.println(arrangeCoins(2));
//        System.out.println(arrangeCoins(3));
//        System.out.println(arrangeCoins(4));
//        System.out.println(arrangeCoins(5));
//        System.out.println(arrangeCoins(6));
//        System.out.println(arrangeCoins(8));
//        System.out.println(arrangeCoins(10));
//        System.out.println(arrangeCoins(1804289383));
        //  System.out.println(arrangeCoins(2147483647));

//        System.out.println(arrangeCoins1(2));
        System.out.println(arrangeCoins1(3));
        System.out.println(arrangeCoins1(4));
        System.out.println(arrangeCoins1(5));
        System.out.println(arrangeCoins1(8));
        System.out.println(arrangeCoins1(10));
        System.out.println(arrangeCoins1(1804289383));
        // System.out.println(arrangeCoins(1804289383));
        System.out.println(arrangeCoins1(2147483647));

//        System.out.println((int) Math.sqrt(1804289383L*2));
        //  System.out.println(((int)Math.sqrt((long)1804289383L*2))*((int)Math.sqrt((long)1804289383L*2)));
    }


}
